package eleven;

import java.util.*;

/**
 * 187. 重复的DNA序列(中等)
 *注意: for里面再使用contains就会变成n^2时间复杂度！！！
 * 巧用 subStrMap.put(substr,subStrMap.getOrDefault(substr,0)+1);//妙
 */
public class Day05 {
    public List<String> findRepeatedDnaSequences(String s) {//for里面再使用contain就会变成n^2时间复杂度！！！
        ArrayList<String> arrayList = new ArrayList<>();
        HashMap<String,Integer> subStrMap = new HashMap<>();

        if (s.length() < 11) return arrayList;

        for (int i = 0; i < s.length()-9; i++){
            String substr = s.substring(i, i + 10);
            subStrMap.put(substr,subStrMap.getOrDefault(substr,0)+1);//妙
            if (subStrMap.get(substr)==2){//substr数量为2就就满足条件
                arrayList.add(substr);
            }
        }

        return arrayList;
    }
    public static void main(String[] args) {
        Day05 day05 = new Day05();
        List<String> stringList = day05.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
        for(String substr:stringList){
            System.out.println(substr);
        }

    }
}
/*
public class Day05 {
    public List<String> findRepeatedDnaSequences(String s) {//超时！！！暴力
        ArrayList<String> arrayList = new ArrayList<>();

        if (s.length() < 11) return arrayList;

        for (int i = 0; i < s.length()-9; i++){
            String substr = s.substring(i, i + 10);
            boolean flat = false;
            for(int j = 1; j < s.length()-9&&j!=i;j++){
                String substr2 = s.substring(j, j + 10);
                if (substr.equals(substr2)){
                    flat = true;//遇到一个相同的 即该子串满足条件
                    break;
                }
            }
            if (flat&&(!arrayList.contains(substr))){//flat为true且不在满足条件的子串列表中
                arrayList.add(substr);
            }
        }
        return arrayList;
    }
    public static void main(String[] args) {
        Day05 day05 = new Day05();
        List<String> stringList = day05.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
        for(String substr:stringList){
            System.out.println(substr);
        }

    }
}
*/